This paper considers the computation of matrix chain products of the form M1 x M2 x ... M(n-1). The order in which the matrices are multiplied affects the number of operations. The best sequential algorithm for computing an optimal order of matrix multiplication runs in O (n log n) time while the best known parallel NC algorithm runs in O (log2n) time using n6/log6n processors. This paper presents the first approximating optimal parallel algorithm for this problem and for the problem of finding a near-optimal triangulation of a convex polygon. The algorithm runs in O (log n) time using n /logn processors on a CREW PRAM, and O ( log log n) time using n / log log n processors on a weak CRCW PRAM. It produces an order of matrix multiplications and a partition of polygon which differ from the optimal ones at most 0.1547 times.
展开▼
机译：本文考虑了M1 x M2 x ... M（n-1）形式的矩阵链乘积的计算。矩阵相乘的顺序会影响运算次数。使用n6 / log6n处理器，用于计算矩阵乘法最佳顺序的最佳顺序算法以O（n log n）时间运行，而最著名的并行NC算法以O（log2n）时间运行。本文针对该问题以及寻找凸多边形的近最佳三角剖分问题提出了第一种近似最佳并行算法。该算法在CREW PRAM上使用n个/ logn处理器以O（log n）时间运行，而在弱CRCW PRAM上使用n个/ log log n处理器以O（log logn）时间运行。它产生一个矩阵乘法的阶数和一个多边形的分区，这些阶数与最佳的相乘最多为0.1547次。
展开▼
